﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace OnlineScheduling.DomainModel
{

    //kopczyk wzięty z jakiejś stronki, widać że fajnie zrobiony, generycznie w C#, to żal nie skorzystać


    /// <summary>
    /// heap data stucture, guaranteed O(nlog n), acts as a priority queue
    /// </summary>
    /// <typeparam name="TValue">
    /// </typeparam>
    public class ProcessorHeap<TValue> where TValue : IComparable
    {
        // functions return if item not found
        public const int NOTFOUND = -1;
        // root offset
        const int ROOT = 0;
        // forward, backward step direction
        const int FORWARD = 1;
        const int BACKWARD = -FORWARD;
        // storage of values
        List<TValue> values = null;
        int[] heapIndexes = null;
        List<int> ids = null;
        // allow parameterisation of ordering and (min/max heap)
        Comparison<TValue> comparison = null;

        /// <summary>
        /// creates a new heap, with ordering
        /// defined by T : IComparable
        /// </summary>
        public ProcessorHeap(int maxSize)
        {
            values = new List<TValue>();
            heapIndexes = new int[maxSize];
            ids = new List<int>();

            for (int i = 0; i < maxSize; i++)
                heapIndexes[i] = -1;
        }

        /// <summary>
        /// creates a new heap, with ordering
        /// defined by Comparison<T>
        /// </summary>
        /// <param name="comparison"></param>
        public ProcessorHeap(Comparison<TValue> comparison, int maxSize)
            : this(maxSize)
        {
            this.comparison = comparison;
        }

        /// <summary>
        /// return the value at offset position in the tree (pre-order traversal)
        /// </summary>
        /// <param name="position">offset in tree</param>
        /// <returns></returns>
        public TValue this[int position]
        {
            get
            {
                return values[position];
            }
        }

        /// <summary>
        /// number of values in tree
        /// </summary>
        public int Count
        {
            get
            {
                return Length();
            }
        }

        /// <summary>
        /// returns the offset of the parent
        /// </summary>
        /// <param name="position">the value position to find parent of</param>
        /// <returns>offset of parent in tree</returns>
        public int ParentOf(int position)
        {
            int result = NOTFOUND;
            if (position > 0)
                result = ((position + 1) / 2) - 1;

            return result;
        }

        /// <summary>
        /// return the offset of the left child
        /// </summary>
        /// <param name="position">the value offset position to find the left child of</param>
        /// <returns>offset of left child in tree</returns>
        public int Left(int position)
        {
            int result = NOTFOUND;

            result = (position * 2) + 1;

            result = EnsureNotBeyond(result);

            return result;
        }

        /// <summary>
        /// return the offset of the right child
        /// </summary>
        /// <param name="position">the value offset position to find the right child of</param>
        /// <returns>offset of right child in tree</returns>
        public int Right(int position)
        {
            // right node is 1 more than the left
            int result = Left(position);

            if (result != NOTFOUND)
                result++; // one position beyond left

            result = EnsureNotBeyond(result);

            return result;
        }

        /// <summary>
        /// returns the root value
        /// </summary>
        public TValue Root
        {
            get
            {
                if (Length() == 0)
                    throw new InvalidOperationException("No items in heap");

                return values[ROOT];
            }
        }

        /// <summary>
        /// returns the value with highest priority
        /// </summary>
        /// <returns>the value</returns>
        public TValue Pop()
        {
            TValue result = Root;

            int lastItem = EnsureNotBeyond(Length() - 1);
            int poppedItem = ids[ROOT];

            if (Length() > 1)
            {            
                values[ROOT] = values[lastItem];
                ids[ROOT] = ids[lastItem];
                heapIndexes[ids[ROOT]] = ROOT;
            }

            values.RemoveAt(lastItem);
            heapIndexes[poppedItem] = -1;
            ids.RemoveAt(lastItem);

            MaintainHeapProperty(FORWARD);

            return result;
        }


        public TValue PopAtSpecificPont(int index)
        {
            TValue result = this[index];

            int lastItem = EnsureNotBeyond(Length() - 1);
            int poppedItem = ids[index];

            if (Length() > 1)
            {
                values[index] = values[lastItem];
                ids[index] = ids[lastItem];
                heapIndexes[ids[index]] = index;
            }

            values.RemoveAt(lastItem);
            heapIndexes[poppedItem] = -1;
            ids.RemoveAt(lastItem);

            MaintainHeapPropertyAtGivenPoint(FORWARD, index);

            return result;
        }

        /// <summary>
        /// add the value to the tree
        /// </summary>
        /// <param name="value">value to add</param>
        public void Push(TValue value, int id)
        {
            values.Add(value);
            heapIndexes[id] = ids.Count;
            ids.Add(id);

            MaintainHeapProperty(BACKWARD);
        }

        public int GetHeapPositionById(int id)
        {
            return heapIndexes[id];
        }

        /// <summary>
        /// number of nodes
        /// </summary>
        /// <returns>length</returns>
        private int Length()
        {
            return values.Count;
        }

        /// <summary>
        /// ensures a  position is not beyond the tree storage
        /// </summary>
        /// <param name="position">offset</param>
        /// <returns>offset, or NOTFOUND if out of bounds</returns>
        private int EnsureNotBeyond(int position)
        {
            if (position >= Length())
                position = NOTFOUND;

            return position;
        }

        /// <summary>
        /// adjusts tree to ensure heap property maintained after a push or pop
        /// </summary>
        /// <param name="direction">FORWARD for push, BACKWARD if pop</param>
        private void MaintainHeapProperty(int direction)
        {
            int start = (direction == FORWARD) ? ROOT : Length();
            int end = (direction == FORWARD) ? Length() : NOTFOUND;

            for (int pos = start; pos != end; pos += direction)
            {
                int left = Left(pos);
                int right = Right(pos);

                // ensure this value is greater than chidren
                if (left != NOTFOUND && Compare(pos, left) < 0)
                    Swap(pos, left);
                if (right != NOTFOUND && Compare(pos, right) < 0)
                    Swap(pos, right);
            }
        }


        private void MaintainHeapPropertyAtGivenPoint(int direction, int location)
        {
            int start = (direction == FORWARD) ? location : Length();
            int end = (direction == FORWARD) ? Length() : NOTFOUND;

            for (int pos = start; pos != end; pos += direction)
            {
                int left = Left(pos);
                int right = Right(pos);

                // ensure this value is greater than chidren
                if (left != NOTFOUND && Compare(pos, left) < 0)
                    Swap(pos, left);
                if (right != NOTFOUND && Compare(pos, right) < 0)
                    Swap(pos, right);
            }
        }
        /// <summary>
        /// return integer indicating order
        /// </summary>
        /// <param name="first">offset of first</param>
        /// <param name="second">offset of second</param>
        /// <returns>.lt. zero=first,second;zero=first==second;.gt. zero=second,first</returns>
        private int Compare(int first, int second)
        {
            int result = 0;

            // if comparison delegate provided us it to compare
            if (comparison != null)
                result = comparison(values[first], values[second]);
            else // default TValue compare
                result = values[first].CompareTo(values[second]);

            return result;
        }

        /// <summary>
        /// swaps two offsets
        /// </summary>
        /// <param name="first">first offset</param>
        /// <param name="second">second offset</param>
        private void Swap(int first, int second)
        {
            TValue temp = values[first];
            values[first] = values[second];
            values[second] = temp;

            int tempInt = ids[first];
            ids[first] = ids[second];
            ids[second] = tempInt;

            heapIndexes[ids[first]] = first;
            heapIndexes[ids[second]] = second;
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();

            sb.Append("[");
            foreach (TValue value in values)
                sb.Append(value.ToString());
            sb.Append("]");

            return sb.ToString();
        }
    }


}
